Digital halftoning is a printing technique widely used to print computer printer-outs, printed books, newspapers and magazines, for example. When printing these materials, original images are changed into halftone images at first. These halftone images can be taken as the original images when viewing from a distance by lowpass filtering in human visual system (HVS). There are various kinds of halftoning methods, including ordered dithering, dot diffusion, error diffusion, direct binary search (DBS) and so on.
The ordered dithering is a parallel processing method, and is generally distinguished into clustered-dot and dispersed-dot halftone screens. The image quality of the ordered dithering is inferior to the DBS, error diffusion, as well as the dot diffusion, since the error induced during the halftoning procedure is retained in each halftone pixel. The image quality of the ordered dithering is worse so that it is hard to be accepted by human beings. Conversely, the error diffusion does not have the above-mentioned problem, because the quantized error is compensated by the neighborhood pixels. However, the error diffusion was born of lacking parallel processing advantage. Hence, the processing efficiency of the error diffusion is much inferior to the ordered dithering. For the time being, the DBS is the most powerful halftoning in the view of image quality. However, the time-consuming iteration-based approach of the DBS makes it difficult to be realized in commercial printing devices, for example, laser printers or inkjet printers.
Among those methods, the dot diffusion is accommodated image quality and processing efficiency. The dot diffusion inherently has the parallel processing benefit by cooperating with the so-called class matrix. So far, the dot diffusion methods proposed by Knuth and Mese are the two most well-known conventional methods. Their researches related to the dot diffusion are focused on class matrix optimization. In the following paragraphs, it will be described the concept of the dot diffusion and the major differences and weaknesses of the two conventional dot diffusion methods.
For an original grayscale image of size P×Q, it is divided into non-overlapping blocks of size M×N. An important media called class matrix, which is of the same size as a divided block, is employed to determine the processing order in a block. Please refer to FIG. 1, which shows a flow chart of the dot diffusion method. Here a white pixel is defined as 255 and a black pixel as 0. The variable xi,j denotes a grayscale value of a pixel as an input and x′i,j is the diffused error accumulated from the neighboring processed pixels. The variable bi,j represents a binary output at position (i,j) and vi,j is the modified gray output. The variable ei,j denotes the difference between the modified gray output vi,j and binary output bi,j, and the relationships of vi,j, bi,j and ei,j are represented as below:
                                          v                          i              ,              j                                =                                    x                              i                ,                j                                      +                          x                              i                ,                j                            ′                                      ,                              where            ⁢                                                  ⁢                          x                              i                ,                j                            ′                                =                                    ∑                              m                =                                  -                  1                                            1                        ⁢                                          ∑                                  n                  =                                      -                    1                                                  1                            ⁢                                                                    e                                                                  i                        +                        m                                            ,                                              j                        +                        n                                                                              ×                                      h                                          m                      ,                      n                                                                      sum                                                                        (        1        )                                                      e                          i              ,              j                                =                                    v                              i                ,                j                                      -                          b                              i                ,                j                                                    ,                              where            ⁢                                                  ⁢                          b                              i                ,                j                                              =                      {                                                                                                      0                      ,                                                                                                                          if                        ⁢                                                                                                  ⁢                                                  v                                                      i                            ,                            j                                                                                              <                      128                                                                                                                                  255                      ,                                                                                                                          if                        ⁢                                                                                                  ⁢                                                  v                                                      i                            ,                            j                                                                                              ≥                      128                                                                                  ,                                                          (        2        )            where the variable hm,n is a diffused weighting. The diffused weightings appearing in Knuth's and Mese's methods are shown in Table 1. A notation x denotes the current processing pixel, and the integers in the eight-neighbor connections are diffused proportions, i.e. the diffused weightings. Since the neighbors in vertical and horizontal orientations are closer to the center, the weightings are greater than those at diagonal orientations.
TABLE 11212x2121
Note that, the error can only diffuse to neighbor pixels that have not binarized yet, which associates to the members in the class matrix with higher value. The variable
  sum  =            ∑              m        =                  -          1                    1        ⁢                  ⁢                  ∑                  n          =                      -            1                          1            ⁢                          ⁢              h                  m          ,          n                    is the summation of the diffused weighings corresponding to those unprocessed pixels. An example shown in FIG. 2 demonstrates the concepts introduced above, where the Knuth's class matrix shown in Table 2 is adopted for reference. For example, a member value 0 can diffuse to 3, 4, 6, 8, 12, 16, 20 and 24, and a member value 7 can diffuse to 10, 15, 18, 23, 31. The values of sum associate to the member values 0 and 7 in the class matrix are 12 and 7, respectively.
TABLE 23448403229152331425856532157105062614513121838465437251792628142230354941332046114359575212031951636044241682739475536The parallel property of the dot diffusion can be appreciated also from FIG. 2, where the pixels associate to the same value in the class matrix can be processed at the same time, i.e. parallel processing. For example, suppose the class matrix is of size 8×8, a dot diffused image can be obtained in 64 time units.
The processing orders within the class matrix have great influence to the reconstructed image quality. Knuth's optimization method tries to reduce the number of baron (pixel with no higher pixel value surrounded) and near-baron (pixel with only one higher pixel value surrounded) in the class matrix. The concept is straight-forward since the baron results in non-diffusible quantized error, and the near-baron only allows the quantized error diffuses in one way. However, the Knuth's method does not take the human visual system (HVS) into consideration. Therefore, it is uncomfortable to view the reconstructed images. For this, Mese's method adopts the following HVS equation into their optimization procedure to determine an optimized order within the class matrix. The shape of the equation in frequency domain is shown in FIG. 3,
                                          H            ⁡                          (                              u                ,                v                            )                                =                                    aL              b                        ⁢                          exp              ⁡                              (                                                      -                                          1                                              s                        ⁡                                                  (                          ϕ                          )                                                                                                      ⁢                                                                                                              u                          2                                                +                                                  v                          2                                                                                                                                    c                        ⁢                                                                                                  ⁢                                                  log                          ⁡                                                      (                            L                            )                                                                                              +                      d                                                                      )                                                    ,                            (        3        )                                          where          ⁢                                          ⁢                      s            ⁡                          (              φ              )                                      =                                            [                                                1                  -                  sum                                2                            ]                        ⁢                          cos              ⁡                              (                                  4                  ⁢                  φ                                )                                              +                                    [                                                1                  +                  sum                                2                            ]                        .                                              (        4        )            The variable a=131.6, b=0.318, c=0.525, d=3.91 and L=0.091 in Mese's work. In addition, the variable sum=0.7 and φ=arctan(u/v). During the optimization, the single tone 16 is employed to develop the final class matrix as shown in Table 3 (8×8) and Table 4 (16×16).
TABLE 3(Mese's 8 × 8)4731512427455213763531122413361057162629468201496218413861713251555485258372323034566028403639494335105423501242594419
TABLE 4(Mese's 16 × 16)2070131728551810281977414414916917017236233656506587145130137158182184195221714243767698651061521501651831922241152643535110111513113913616611920822322642239527184103164135157173113190222225227164085728310411716713316818020021923122812214712054105123132146176179202220230245220417673127109138134178181206196229244246194249809911214714217117720321823224324824733486810810714014318516320421723324224925544457079110141887517520521423424125025438467711610011114816017420121523524025125225361629394125151159189199197216236239253160829295124114156188191209213237238293259649111878128155187194198212910303558639096122129154161193210211811273457668998121126153162186
However, in Mese's method, the diffused weightings are not optimized. The reconstructed image quality is thus limited. Mese solely uses single tone of value 16 to optimize the class matrix. This causes the reconstructed class matrix difficult to perfectly render image regions with different tones.
Above all, the ordered dithering, error diffusion and DBS have drawbacks mentioned above. The dot diffusion, such as well-known conventional Knuth's and Mese's methods, still remains rooms for improving halftone image quality. Consequently, there is a need to develop a method for improving the reconstructed halftone image quality, at the same time, preserving the property of parallel processing.